#include <iostream>
#include <vector>

template <typename T> class BinarySearchTree
{
public:
    BinarySearchTree( );
    BinarySearchTree( const BinarySearchTree & rhs );
    BinarySearchTree( BinarySearchTree && rhs );
    ~BinarySearchTree( );
    const T & findMin( ) const;
    const T & findMax( ) const;
    bool contains( const T & x ) const;
    bool isEmpty( ) const;
    void printTree( std::ostream & out = std::cout ) const;
    void flatten( std::vector<T> & ) const;

    void makeEmpty( );
    void insert( const T & x );
    void insert( T && x );
    void remove( const T & x );

    BinarySearchTree & operator=( const BinarySearchTree & rhs );
    BinarySearchTree & operator=( BinarySearchTree && rhs );

private:
    struct BinaryNode
    {
        T element;
        BinaryNode *left;
        BinaryNode *right;
        BinaryNode( const T & theElement, BinaryNode *lt, BinaryNode *rt )
            : element{ theElement }, left{ lt }, right{ rt } { }

        BinaryNode( T && theElement, BinaryNode *lt, BinaryNode *rt )
            : element{ std::move( theElement ) }, left{ lt }, right{ rt } { }
    };
    BinaryNode *root;

    void insert( const T & x, BinaryNode * & t );
    void insert( T && x, BinaryNode * & t );
    void remove( const T & x, BinaryNode * & t );
    BinaryNode * findMin( BinaryNode *t ) const;
    BinaryNode * findMax( BinaryNode *t ) const;
    bool contains( const T & x, BinaryNode *t ) const;
    void makeEmpty( BinaryNode * & t );
    void printTree( BinaryNode *t, std::ostream & out ) const;
    BinaryNode * clone( BinaryNode *t ) const;
    void flatten( BinaryNode *t, std::vector<T> & arr ) const;
};

template <typename T> BinarySearchTree<T>::BinarySearchTree( )
{
    root = nullptr;
}

template <typename T> BinarySearchTree<T>::BinarySearchTree( const BinarySearchTree & rhs )
{
    root = clone(rhs.root);
}

template <typename T> BinarySearchTree<T>::BinarySearchTree( BinarySearchTree && rhs )
{
    root = rhs.root;
    rhs.root = nullptr;
}

template <typename T> BinarySearchTree<T>::~BinarySearchTree( )
{
    makeEmpty();
}

template <typename T> const T & BinarySearchTree<T>::findMin( ) const
{
    BinaryNode * minNode = findMin(root);
    return minNode->element;
}

template <typename T> const T & BinarySearchTree<T>::findMax( ) const
{
    BinaryNode * maxNode = findMax(root);
    return maxNode->element;
}

template <typename T> bool BinarySearchTree<T>::contains( const T & x ) const
{
    return contains(x, root);
}

template <typename T> bool BinarySearchTree<T>::isEmpty( ) const
{
    return root == nullptr;
}

template <typename T> void BinarySearchTree<T>::printTree( std::ostream & out ) const
{
    printTree( root, out );
}

template <typename T> void BinarySearchTree<T>::makeEmpty( )
{
    makeEmpty( root );
}

template <typename T> void BinarySearchTree<T>::insert( const T & x )
{
    insert(x, root);
}

template <typename T> void BinarySearchTree<T>::insert( T && x )
{
    insert(x, root);
}

template <typename T> void BinarySearchTree<T>::remove( const T & x )
{
    remove(x, root);
}

template <typename T> void BinarySearchTree<T>::flatten( std::vector<T> & arr ) const
{
    arr.clear();
    flatten( root, arr );
}

template <typename T> BinarySearchTree<T> & BinarySearchTree<T>::operator=( const BinarySearchTree & rhs )
{
    BinarySearchTree copy = rhs;
    std::swap(*this, copy);
    return *this;
}

template <typename T> BinarySearchTree<T> & BinarySearchTree<T>::operator=( BinarySearchTree && rhs )
{
    std::swap(root, rhs.root);
    return *this;
}

template <typename T> void BinarySearchTree<T>::insert( const T & x, BinaryNode * & t )
{
    if( t == nullptr )
        t = new BinaryNode( x, nullptr, nullptr );
    else if( x <= t->element )
        insert( x, t->left );
    else
        insert( x, t->right );
}

template <typename T> void BinarySearchTree<T>::insert( T && x, BinaryNode * & t )
{
    if( t == nullptr )
        t = new BinaryNode( std::move( x ) , nullptr, nullptr );
    else if( x <= t->element )
        insert( x, t->left );
    else
        insert( x, t->right );
}

template <typename T> void BinarySearchTree<T>::remove( const T & x, BinaryNode * & t )
{
    if( t == nullptr )
        return;
    else if( x < t->element )
        remove( x, t->left );
    else if( x > t->element )
        remove( x, t->right );
    else
    {
        if( t->left == nullptr || t->right == nullptr )
        {
            BinaryNode * tmp = t;
            t = t->left | t->right;
            delete tmp;
        }
        else
        {
            BinaryNode * leftMax = findMax( t->left );
            t->element = leftMax->element;
            remove( leftMax->element, t->left );
        }
    }
}

template <typename T> typename BinarySearchTree<T>::BinaryNode * BinarySearchTree<T>::findMin( BinaryNode *t ) const
{
    if( t == nullptr )
        return nullptr;
    else if( t->left == nullptr )
        return t;
    else
        return findMin( t->left );
}

template <typename T> typename BinarySearchTree<T>::BinaryNode * BinarySearchTree<T>::findMax( BinaryNode *t ) const
{
    if( t == nullptr )
        return nullptr;
    else if( t->right == nullptr )
        return t;
    else
        return findMax( t->right );
}

template <typename T> bool BinarySearchTree<T>::contains( const T & x, BinaryNode *t ) const
{
    if( t == nullptr )
        return false;
    else if( t->element == x )
        return true;
    else
        return ( x < t->element ) ? contains( x, t->left ) : contains( x, t->right );
}

template <typename T> void BinarySearchTree<T>::makeEmpty( BinaryNode * & t )
{
    if( t == nullptr )
        return;
    makeEmpty( t->left );
    makeEmpty( t->right );
    BinaryNode * tmp = t;
    delete tmp;
    t = nullptr;
}

template <typename T> void BinarySearchTree<T>::printTree( BinaryNode *t, std::ostream & out ) const
{
    if( t == nullptr )
        return;
    printTree( t->left, out );
    out << t->element << ' ';
    printTree( t->right, out );
}

template <typename T> typename BinarySearchTree<T>::BinaryNode * BinarySearchTree<T>::clone( BinaryNode *t ) const
{
    if( t == nullptr )
        return nullptr;
    BinaryNode * newnode = new BinaryNode( t->element, nullptr, nullptr );
    newnode->left = clone( t->left );
    newnode->right = clone( t->right );
    return newnode;
}

template <typename T> void BinarySearchTree<T>::flatten( BinaryNode *t, std::vector<T> & arr ) const
{
    if( t == nullptr )
        return;
    flatten( t->left, arr );
    arr.push_back( t->element );
    flatten( t->right, arr );
}
